package Solution101_200.problem113.PathSumII;

import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/07/15 12:06
 */
public class Solution {
    List<List<Integer>> result=new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null){
            return result;
        }
        sumValue(root,0,sum,new ArrayList<>());
        return result;
    }


    private void sumValue(TreeNode root, int temp,int sum,List<Integer> tempList) {
        temp = temp + root.val;
        tempList.add(root.val);
        List<Integer> newList=new ArrayList<>(tempList);

        if (root.left == null && root.right == null) {
            if(temp==sum){
                result.add(newList);
            }
        } else if (root.left == null) {
            sumValue(root.right, temp,sum,newList);
            newList.remove(newList.size()-1);
        } else if (root.right == null) {
            sumValue(root.left, temp,sum,newList);
            newList.remove(newList.size()-1);
        } else {
            sumValue(root.right, temp,sum,newList);
            newList.remove(newList.size()-1);
            sumValue(root.left, temp,sum,newList);
            newList.remove(newList.size()-1);
        }
    }
}
